package 力扣日常刷题.木22一月.第05天0112;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author 帅小伙
 * @date 2022/1/12
 * @description
 */
public class Demo01回溯中等有重复字符串的排列组合 {


    char[] chars;
    ArrayList<String> ans = new ArrayList<>();
    boolean[] isUsed;
    public String[] permutation(String S) {
        chars = S.toCharArray();
        isUsed = new boolean[chars.length];
        Arrays.sort(chars);
        dfs(0,new StringBuffer());
        return ans.toArray(new String[ans.size()]);
    }

    void dfs(int index,StringBuffer sb){
        if(index ==  chars.length){
            ans.add(sb.toString());
            return ;
        }

        char last = '*';
        for (int i = 0; i < chars.length; i++) {
            if(!isUsed[i] && chars[i]!=last){
                isUsed[i] = true;
                sb.append(chars[i]);
                dfs(index+1,sb);
                isUsed[i] = false;
                last = chars[i];
                sb.deleteCharAt(sb.length()-1);
            }
        }




    }

}
